package LRU;

import lombok.Data;

import java.util.*;


/**
 * LRU：Least Recently Used 最少使用策略，判断最近被使用的时间，距离目前最远的数据优先被淘汰。（关注使用时间）
 * LFU：Least Frequently Used，最不经常使用策略，在一段时间内，数据被使用频次最少的，优先被淘汰。（同时关注使用次数）
 * <p>
 * 问题：
 * 1. sort()方法排序效率低，清除caches Map全部数据然后再重新存入？线上是不可能这样做的
 * 2. 线程安全问题
 *
 * @author K
 * @date 2021/7/5 上午9:57
 */
@Data
@SuppressWarnings("unchecked")
public class LFU<K, V> {

    /**
     * LFU初始容量
     */
    private int capacity;

    /**
     * 所有节点缓存（使用Node.compareTo()方法比较过的有序Map）
     */
    private Map<K, Node> caches;

    public LFU(int size) {
        this.capacity = size;
        this.caches = new LinkedHashMap<>(size);
    }

    public V get(K key) {
        Node currentNode = caches.get(key);
        if (currentNode != null) {
            currentNode.setCount(currentNode.getCount() + 1);
            currentNode.setTime(System.nanoTime());
            // 重新排序
            sort();
            return (V) currentNode.getValue();
        }
        return null;
    }

    public void put(K key, V value) {
        Node currentNode = caches.get(key);

        if (currentNode == null) {
            // 节点不存在 比较容量，容量不充足-删除最少使用的；最后存放节点；
            if (caches.size() > capacity) {
                removeLeastNode();
            }
            currentNode = new Node(key, value, System.nanoTime(), 1);
            caches.put(key, currentNode);
        } else {
            // 节点存在 更新节点数据
            currentNode.setValue(value);
            currentNode.setCount(currentNode.getCount() + 1);
            currentNode.setTime(System.nanoTime());
        }
        // 重新排序
        sort();
    }

    private void sort() {
        ArrayList<Map.Entry<K, Node>> list = new ArrayList<>(caches.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<K, Node>>() {
            @Override
            public int compare(Map.Entry<K, Node> o1, Map.Entry<K, Node> o2) {
                // 降序 大的放前面
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        // 清除全部缓存，重新存放
        caches.clear();
        for (Map.Entry<K, Node> kNodeEntry : list) {
            caches.put(kNodeEntry.getKey(), kNodeEntry.getValue());
        }
    }

    private void removeLeastNode() {
        Collection<Node> values = caches.values();
        Node min = Collections.min(values);
        caches.remove((K) min.getKey());
    }

}
